Exercise: Graphs
Find if an AdjacencyMatrix has a universal sink.
We'll cover the following
Task#
A universal sink in a graph is a vertex that is the target of edges and the source of no edges. Design and implement an algorithm that tests if a graph , represented as an AdjacencyMatrix, has a universal sink. Your algorithm should run in time.
Sample input
The sample input will be as follows:
(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)
Expected output
The expected output will be as follows:
Universal Sink not found.
Vertex 4 is a Universal Sink in graph.
Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.
Good luck!
Note: You must implement the method
find_uni_sink_on()in the below code starting at line 52.
main.py
utils.py
Implementation to find universal sink in a graph
Discussion on Graphs
Solution: Graphs